package com.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: sun.hongliang
 * @create: 2019/07/29 10:32
 */
public class GenerateParenthesis {
    public static void main(String[] args) {
        GenerateParenthesis c = new GenerateParenthesis();
        List<String> strings = c.generateParenthesis(14);
        System.out.println(strings);
    }

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateAll(new char[n * 2], 0, result);
        return result;
    }

    private void generateAll(char[] chars, int i, List<String> result) {
        if (i == chars.length) {
            boolean valid = valid(chars);
            if (valid) {
                result.add(new String(chars));
            }
        } else {
            chars[i] = '(';
            generateAll(chars, i + 1, result);
            chars[i] = ')';
            generateAll(chars, i + 1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }
}
